#include <stdio.h>
#include <string.h> //memset strncpy
#include "huffman.h"
#include "heap.h"
#include "../draw.h"
#include "../myTypes.h"
#include "../barre.h"
#include "../pretraitement/bwt.h"


#define TREEMAXSIZE ((2*MAXCAR)-1)

float upBar; //variable globale de la barre de progression

typedef struct htree{
	byte b;				//caractère
	int	 weight;		//poid du noeud (i)
	struct htree * l;	//fils gauche
	struct htree * r;	//fils droit
	struct htree * up;	//père
}htree_t;

typedef struct huffcode{
	bloc_t		bits[MAXCAR/32];	//logueur de code max en bits = MAXCAR-1
	bitcount_t	len;
}huffcode_t;


static htree_t mem_tree[TREEMAXSIZE];
static int allocated;
static htree_t * root;	//racine de l'arbre


void HuffTree_draw(htree_t * root, char * filename);

//-----------------------------------------------------------------------------
void HUFF_init()
//-----------------------------------------------------------------------------
{
	allocated = MAXCAR;
	memset(mem_tree,0, TREEMAXSIZE*sizeof(htree_t));
}


//Fusionner deux sous arbres NON VIDES
//-----------------------------------------------------------------------------
htree_t * HUFF_fusion( htree_t * l, htree_t * r)
//-----------------------------------------------------------------------------
//Complexité O(1)
{
	//htree_t * t = (htree_t *)malloc(sizeof(htree_t));
	htree_t * t = &mem_tree[allocated++];	//mémoire "pré-allouée"
	t->l		= l;
	t->r		= r;
	t->up		= NULL;
	t->b		= 0; //pour un éventuel affichage de l'arbre
	t->weight	= l->weight + r->weight;
	l->up = t; r->up = t;

	return t;
}


// Contruction de l'arbre de codage O(n.logn)
//-----------------------------------------------------------------------------
void HUFF_buildHTree(int freqTab[MAXCAR])
//-----------------------------------------------------------------------------
{
	int i=0;
	heap_t	heap;
	htree_t	* n=NULL,* m=NULL;

	//initialisation du tas
	heap_init(&heap,MAXCAR);

	//initialisation des feuilles de l'arbre
	while(i<MAXCAR)
	{
		mem_tree[i].b	= (byte)i;
		mem_tree[i].weight	= freqTab[i];

		//entasser les feuilles utiles
		if(freqTab[i]>0) heap_push(&heap,freqTab[i], (void *)&mem_tree[i]);

		i++;
	}

	//construction de l'arbre O(n.logn)
	//FIXME éviter la segfault lorsqu'on a qu'un seul élément dans le tas !!!
	do{
		n = heap_getMin(&heap); heap_pop(&heap); //hip_hop() ouésh ouésh ... ou pas :D
		m = heap_getMin(&heap); heap_pop(&heap);
		root = HUFF_fusion(n,m);
		heap_push(&heap, root->weight, (void *)root);

	}while( heap.size > 1 );

	//Dessin de l'arbre
	HuffTree_draw(root, "Huffman.ps");
}


//fonction récursive utilisée par HUFF_exportHTree()
//-----------------------------------------------------------------------------
static void tree2bitbuf(htree_t * t, bitbuf_t * dst )
//-----------------------------------------------------------------------------
{
	if(t->l) //si T est un noeud
	{
		bit_put0(dst); //N
		tree2bitbuf(t->l,dst);
		tree2bitbuf(t->r,dst);
	}else{	// T est une feuille
		bit_put1(dst); //F
		bit_write(dst,(bloc_t)t->b,8);
	}

}


//fonction récursive utilisée par HUFF_importHTree()
//-----------------------------------------------------------------------------
static void bitbuf2tree(htree_t * t, bitbuf_t * src )
//-----------------------------------------------------------------------------
{
	if(bit_get(src) == 0 ) //si on lit un N
	{
		//créer les deux fils
		t->l = &mem_tree[allocated++];
		t->r = &mem_tree[allocated++];
		t->l->up = t;
		t->r->up = t;
		bitbuf2tree(t->l,src);
		bitbuf2tree(t->r,src);
	}else{	// on lit un F
		// lire la valeur de la feuille
		t->b = (byte)bit_read(src,8);
		t->weight = 0; t->l =NULL; t->r =NULL;
	}

}


//Exporter un arbre de codage dans un buffer
//-----------------------------------------------------------------------------
void HUFF_exportHTree( bitbuf_t * dst )
//-----------------------------------------------------------------------------
{
	bit_seek(dst,0,0,BITSEEK_SET);
	tree2bitbuf(root,dst);
	dst->len = bit_getpos(dst);
}


//Importer un arbre de codage depuis un buffer
//-----------------------------------------------------------------------------
void HUFF_importHTree( bitbuf_t * src )
//-----------------------------------------------------------------------------
{
	allocated=0;
	root = &mem_tree[allocated++];
	bitbuf2tree(root,src);
}


//-----------------------------------------------------------------------------
bitcount_t HUFF_readCode(bitbuf_t * src, byte * b)
//-----------------------------------------------------------------------------
{
	bitcount_t	res=0;
	htree_t *	n=root;

	while(n->l)	//tanqu'on est pas sur une feuille
	{
		res++;
		if( bit_get(src) == 0 )
			n= n->l;	//prendre a gauche
		else
			n= n->r;	//prendre a droite
	}

	*b=n->b;

	return res;
}


//-----------------------------------------------------------------------------
static bitcount_t huff_writeCodeRec(htree_t * node, bitbuf_t * buf)
//-----------------------------------------------------------------------------
{
	bitcount_t res=0;

	if(!node->up) return 0;	//Écrire 0 bis pour la racine

	res = 1 + huff_writeCodeRec(node->up, buf);

	if(node->up->l == node)	//fils gauche
		bit_put0(buf);		// Ecrire 0
	else
		bit_put1(buf);		// Ecrire 1

	return res;
}


//Écrire le code de b dans le buffer, retourne le nombre de bits
//-----------------------------------------------------------------------------
bitcount_t HUFF_writeCode(bitbuf_t * dst, byte b)
//-----------------------------------------------------------------------------
{
	//TODO Mettre en place un cache pour ne pas recalculer le code à chaque fois
	// ou pas ... car les codes les plus fréquent sont par principe les plus courts
	// avec la méthode de huffman
	return huff_writeCodeRec(&mem_tree[b], dst);
}


#define RAYON 10
//-------------------------------------------------------------------------------
static void draw_recursif(htree_t *arbre, int gauche, int droite, int hauteur)
//-------------------------------------------------------------------------------
{
	if (arbre)
	{
		int		m=(droite-(droite-gauche)/2);
		vec2_t	v={ m-3, hauteur+3 };
		vec2_t	v2={ m-5, hauteur-5 };
		cir_t	noeud={ {m, hauteur} , RAYON };
		cir_t	fils;

		char car[2];
		char freq[10];

		DrawCir(&noeud);
		car[0]=arbre->b, car[1]= '\0';
		DrawText(v,car);

		snprintf(freq,9,"%d",arbre->weight);
		DrawText(v2,freq);

		draw_recursif(arbre->l,gauche,m,hauteur-20);
		draw_recursif(arbre->r,m,droite,hauteur-20);

		if(arbre->l)
		{
			fils.c[0]=gauche+(m-gauche)/2;fils.c[1]=hauteur-20;fils.r=RAYON;
			DrawLink(&noeud,&fils);
			fils.c[0]=m+(droite-m)/2;fils.c[1]=hauteur-20;fils.r=RAYON;
			DrawLink(&noeud,&fils);
		}

	}
}


//Exporte l'abre de huffman au format PS
//-----------------------------------------------------------------------------
void HuffTree_draw(htree_t * root, char * filename)
//-----------------------------------------------------------------------------
{
	FILE * f=NULL;
	if ( (f=fopen(filename,"wb")) )
	{

		PS_option_t options;
		options.fd = f;
		options.h = 300;
		options.w = 500;

		InitDraw((void*) &options);


		draw_recursif(root,0,500, 285);


		fclose(f);
	}
	else perror("HuffTree_draw()");
}


//-----------------------------------------------------------------------------
void HUFF_encode(bitbuf_t * dst, bitbuf_t * src)
//-----------------------------------------------------------------------------
{
	size_t i=0;

	for(i=0;  i < src->len/8; i++)
	{
		huff_writeCodeRec(&mem_tree[src->data[i]],dst);
	}

	dst->len = bit_getpos(dst);

}


//-----------------------------------------------------------------------------
void HUFF_decode(bitbuf_t * dst, bitbuf_t * src)
//-----------------------------------------------------------------------------
{
	size_t i=0;
	byte	b;

	while(i < src->len)
	{
		i += HUFF_readCode(src,&b);
		bit_write(dst,(bloc_t)b,8);
	}

	dst->len = bit_getpos(dst);
}


//-----------------------------------------------------------------------------
int HUFF_writeHeader(FILE * out, huffheader * header)
//-----------------------------------------------------------------------------
{
	int treebufLen = (header->treebuf.len/8)+1;

	//bit_print(&header->treebuf);

	fwrite(header->id,4,1,out);
	fwrite(&header->oriSize,4,1,out);
	fwrite(&header->treebuf.len, 2, 1, out);
	fwrite(header->treebuf.data, treebufLen, 1, out);

	return 10+treebufLen;
}

//-----------------------------------------------------------------------------
void HUFF_readHeader(FILE * in, huffheader * header)
//-----------------------------------------------------------------------------
{
	header->oriSize =0;
	header->treebuf.len = 0;

	fread(header->id,4,1,in);
	fread(&header->oriSize,4,1,in);
	fread(&header->treebuf.len, 2, 1, in);
	fread(header->treebuf.data, (header->treebuf.len/8)+1, 1, in);
}


//-----------------------------------------------------------------------------
void HUFF_compress(FILE * out, FILE * in, char * headerID)
//-----------------------------------------------------------------------------
{
	bitbuf_t src,dst;
	int bufLen = 8192;
	int len=0,i;
	size_t read=0,wrote=0;
	size_t fileLen;
	int freq[MAXCAR]; //table de fréquence pour huffman
	huffheader header;

	//initialisation des buffers
	bit_initBuf(&src,(bufLen+2)*8);
	bit_initBuf(&dst,(bufLen+(bufLen/3))*8);
	bit_initBuf(&header.treebuf, ((MAXCAR*2)+1)*8);

	//initialisation de la table de fréquence
	printf("Calcul de la table des fréquences ...\n");
	memset(freq,0,MAXCAR*sizeof(int));
	while(!feof(in))
	{
		src.len=fread(src.data,1,bufLen,in);
		for(i=0; i<src.len; i++) freq[src.data[i]]++;
	}

	//calcul de la taille du fichier
	fileLen = ftell(in);
	rewind(in);

	printf("filLen= %d\n",fileLen);

	//initialisation de l'algo
	HUFF_init();

	//construction de l'arbre à partir de la table de fréquence
	HUFF_buildHTree(freq);

	//HuffTree_draw(root,"huff.ps");

	//exportation de l'arbre pour le mettre dans l'en-tête
	HUFF_exportHTree(&header.treebuf);
	printf("arbre header = %d bits\n",header.treebuf.len);

	//écriture du header
	strncpy(header.id,headerID,4);
	header.oriSize= fileLen;
	wrote = HUFF_writeHeader(out,&header);

	updateBar(0.);

	while(!feof(in))
	{
		len=fread(src.data, 1, bufLen, in);
		read += len;
		src.len=8*len;	//1octet = 8bits

		updateBar((double)read/fileLen);
		printf(" (%02d%%)",(int)( 100.*( (double)wrote/(double)read)));


		bit_seek(&src,0,0,BITSEEK_SET);
		bit_seek(&dst,0,0,BITSEEK_SET);

		HUFF_encode(&dst,&src);

		fwrite(&dst.len,3, 1, out);
		fwrite(dst.data, ((dst.len)/8)+1,1,out);
		wrote += 3+(dst.len/8)+1;
	}
	updateBar(1.);printf(" (%02d%%)",(int)( 100.*( (double)wrote/(double)read)));
	printf("\n :D\n");

	bit_freeBuf(&src);
	bit_freeBuf(&dst);
	bit_freeBuf(&header.treebuf);
}


//-----------------------------------------------------------------------------
void HUFF_decompress(FILE * out, FILE * in)
//-----------------------------------------------------------------------------
{
	bitbuf_t src,dst;
	int bufLen=8192;
	size_t wrote=0;
	huffheader header;
	size_t fileLen;

	//initialisation des buffers
	bit_initBuf(&src,(bufLen+(bufLen/3))*8);
	bit_initBuf(&dst,(bufLen+2)*8);
	bit_initBuf(&header.treebuf,2*MAXCAR*8);

	//Lecture de l'en-tête
	HUFF_readHeader(in,&header);

	fileLen=header.oriSize; // taille du fichier d'origine
	printf(" oriSize=%ldbytes\n",fileLen);

	//initialisation de l'algo
	HUFF_init();

	//Reconstruction de l'arbre depuis l'en-tête
	HUFF_importHTree(&header.treebuf);
	//HuffTree_draw(root,"hufdecomp.ps");

	updateBar(0.);

	while( !feof(in) )
	{
		src.len=0;
		fread(&(src.len), 3,1,in);
		fread(src.data, 1, (src.len/8)+1, in);

		updateBar((double)wrote/header.oriSize);

		bit_seek(&src,0,0,BITSEEK_SET);
		bit_seek(&dst,0,0,BITSEEK_SET);

		HUFF_decode(&dst, &src);

		fwrite(dst.data, dst.len/8 , 1, out);	//dst.len = 8*k
		wrote+=dst.len/8;
	}
	updateBar((double)wrote/header.oriSize);

	printf("\n :D\n");
	bit_freeBuf(&src);
	bit_freeBuf(&dst);
	bit_freeBuf(&header.treebuf);
}


/*
int main()
{
	int freqTab[MAXCAR];
	int i;
	bitbuf_t	buf;

	bit_initBuf(&buf,256*2*8);
	for(i=0;i<MAXCAR;i++)freqTab[i]=0;
	for(i='a';i<'j';i++)freqTab[i]=(i%2)?(i%14)*(i%6):0;

	HUFF_init();
	HUFF_buildHTree(freqTab);
	HUFF_exportHTree(&buf);
	bit_seek(&buf,0,0,BITSEEK_SET);
	HUFF_importHTree(&buf);
	HuffTree_draw(root,"bufftree.ps");


	return 0;
}
*/

//
